Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Кафедра програмного забезпечення
Курсова робота
з курсу “Методи та засоби комп’ютерних
інформаційних технологій”
ЛЬВІВ – 2004
Зміст
Постановка задачі 3
Теоретичні відомості до завдання № 1 4
Розв’язання завдання № 1 5
Теоретичні відомості до завдання № 2 6
Розв’язання завдання № 2 7
Теоретичні відомості до завдання № 3 9
Розв’язання завдання № 3 10
Текст програми 12
Висновок 14
(Варіант № 18)
Постановка задачі
Завдання № 1
Задана матриця ймовірностей системи, об‘єднаної в одну з двох систем А і В.
P(A,B) =
Визначити повні умовні ентропії H(B/A) і H(A/B).
Завдання № 2
Визначити еквівалентний опір трьох паралельних ланок для заданих параметрів схеми: R1 = 40 Ом; R2 = 50 Ом; R3 = 25 Ом; U = 1,5 B;
I
I1 I2 I3
U R1 R2 R3
Дослідити чутливість струму I3 від параметрів R1, R2, R3. Побудувати залежності ΔI від ΔR1, ΔR2, ΔR3.
Завдання № 3
Написати програму, яка формує перевірочна позиції коду Хемінга для довільного числа коректуючих позицій. Вивести на друк перевірочні позиції для перших п‘яти перевірок.
Теоретичні відомості до завдання № 1
Загальне число повідомлень, що не повторяються, і яке може бути складене з алфавіта m шляхом комбінування по n символів в повідомленні:
N = mn (1)
Невизначеність, що припадає на символ початкового алфавіта, складеного із рівноймовірних і незалежних символів:
H = log m (2)
Основа логарифму впливає лише на зручність обчислень. У випадку оцінки ентропії:
в війкових одиницях H = log2m біт/символ;
в десяткових одиницях H = lgm діт/символ, де log2m = 3.32lgm, 1 біт ≈ 0.3 діт;
в натуральних одиницях H = lnm нат/символ, де log2m = 1.443lnm, 1 біт = 0.693 нат.
Кількість інформації можна зобразити як добуток загального числа повідомлень k і середньої ентропії одного повідомлення:
I = kH біт (3)
Для випадків рівноймовірних і навзаємнезалежних символів вихідного алфавіту кількість інформації в k повідомленнях алфавіту m :
I = klog2m біт (4)
Для нерівно ймовірних алфавітів ентропія на символ алфавіту
біт/символ, (5)
а кількість інформації в повідомленні, складеному з k нерівно ймовірних символів:
біт. (6)
Кількість інформації визначається виключно характеристиками вихідного алфавіту. Об’єм – характеристика вторинного алфавіту. Об’єм інформації
Q = klcp, (7)
де lcp – середня довжина кодових слів вторинного алфавіту. Для рівномірних кодів (всі комбінації коду містять одинакову кількість розрядів)
Q = kn, (8)
де – довжина коду. Таким чином об’єм рівний кількості інформації, якщо lcp = H, тобто у випадку максимального інформаційного навантаження на символ повідомлення.
В загальному випадку ентропія – це кількість інформації на одиин стан системи. Якщо ентропія мала, то невизначеність відсутня.
Основні властивості ентропії:
Ентропія є неперервною і додатною функцією своїх аргументів (H>0).
Ентропія приймає мінімальне значення у двох випадках:
Якщо повідомлення формується за допомогою однієї ознаки, ймовірність появи якої рівне одиниці.
Якщо ймовірність i-ї ознаки приблизно рівна нулю.
Ентропія досягає максимуму, коли всі випадки рівноможливі.
Ентропія повідомлення, що складається з окремих повідомлень дорівнює сумі ентропій повідомлень [H(A,B) = H(A) +H(B)].
Розв’язання завдання № 1
Обчислимо безумовні ймовірності P(ai) та P(bj):
P(ai) = P(bj)=
- ) Визначемо умовні ймовірності p(ai/bj) =
p(a1/ b1) == 0,6 p(a1/ b2) =0 p(a1/ b3) =0
p(a2/ b1) == 0,4 p(a2/ b2) == 0,75 p(a2/ b3) == 1
p(a3/ b1) = 0 p(a3/ b2) == 0,25 p(a3/ b3) =0
P(ai/bj) = H(A/B) =
H(A/B) = - (0,5(0,6log20,6 + 0,4log20,4) + 0,4(0,75log20,75 + 0,25log20,25) + 0,1log20,1)) ≈ 0,485 + 0,324 ≈ 0,809 біт/символ.
- ) Визначемо умовні ймовірності p(bj/ai) =
p(b1/a1) = = 1 p(b1/a2)== 0,333 p(b1/a3) = 0
p(b2/a1) = 0 p(b2/a2)= = 0,5 p(b2/a3) = = 1
p(b3/a1) = 0 p(b3/a2)== 0,167 p(b3/a3) = 0
P(bj/ai) = H(B/A) =
H(A/B) = - 0,6(0,333log20,333 ...